package club.xiaojiawei.back;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/20/22 7:35 PM
 * @question 216. 组合总和 III
 * @description 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 * 只使用数字1到9
 * 每个数字 最多使用一次
 * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 */
public class CombinationSum3216 {

    public static void main(String[] args) {
        CombinationSum3216 test = new CombinationSum3216();
        List<List<Integer>> result = test.combinationSum32(3, 9);
        System.out.println(result);
    }

    /**
     * 递归
     * 时间复杂度：O({M , k} * k)
     * 空间复杂度O(M)
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        recursion(k, n, 1);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();
    int amount = 0;

    List<Integer> tempList = new ArrayList<>();

    public void recursion(int count, int num, int startIndex){
        count--;
        for (int i = startIndex; i <= 9 - count && amount + i <= num; i++){
            amount += i;
            tempList.add(i);
            if (count == 0){
                if (amount == num){
                    result.add(new ArrayList<>(tempList));
                    amount -= tempList.remove(tempList.size() - 1);
                    return;
                }
            }else {
                recursion(count, num, i + 1);
            }
            amount -= tempList.remove(tempList.size() - 1);
        }
    }

    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    /**
     * 官方-二进制
     * 时间复杂度：O(M * 2^M)
     * 空间复杂度O(M)
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum32(int k, int n) {
        for (int mask = 0; mask < (1 << 9); ++mask) {
            if (check(mask, k, n)) {
                ans.add(new ArrayList<Integer>(temp));
            }
        }
        return ans;
    }

    public boolean check(int mask, int k, int n) {
        temp.clear();
        for (int i = 0; i < 9; ++i) {
            if (((1 << i) & mask) != 0) {
                temp.add(i + 1);
            }
        }
        if (temp.size() != k) {
            return false;
        }
        int sum = 0;
        for (int num : temp) {
            sum += num;
        }
        return sum == n;
    }

}
